package com.kitty.record.kittyalgorithm.ds.tree;

import java.util.Objects;

/**
 * @author shenshen.qian@amh-group.com
 * @version 0.0.1
 * @date 2022/2/15 20:44
 */
public class MyAvlTree {

    private MyTreeNode mRoot;


    public MyAvlTree() {
        mRoot = null;
    }


    /**
     * 获取当前数的高度
     *
     * @return
     */
    public int height() {
        return height(mRoot);
    }

    /**
     * 根据树节点获取树的高度
     *
     * @param tree
     * @return
     */
    private int height(MyTreeNode tree) {
        if (!Objects.isNull(tree)) {
            return tree.height;
        }
        return 0;
    }

    /**
     * 根据key查找节点
     *
     * @param key
     * @return
     */
    public MyTreeNode search(int key) {
        return search(mRoot, key);
    }

    /**
     * 根据传入的tree，查找tree下的key节点
     *
     * @param tree
     * @param key
     * @return
     */
    private MyTreeNode search(MyTreeNode tree, int key) {
        while (tree != null) {
            if (key > tree.key) {
                tree = tree.right;
            } else if (key < tree.key) {
                tree = tree.left;
            }
            return tree;
        }
        return null;
    }

    /**
     * 向树中添加系欸但
     *
     * @param key
     */
    public void addKey(int key) {
        MyTreeNode node = new MyTreeNode(key, null, null);
        mRoot = add(mRoot, node);
    }

    /**
     * 向树中添加key节点
     * 此处使用递归方式实现（可以考虑非递归的方式实现）
     *
     * @param tree
     * @param node
     */
    private MyTreeNode add(MyTreeNode tree, MyTreeNode node) {
        if (tree == null) {
            tree = node;
        } else {
            if (node.key > tree.key) {
                tree.right = add(tree.right, node);
                if (height(tree.right) - height(tree.left) == 2) {
                    if (node.key > tree.right.key) {
                        tree = rightRightRot(tree);
                    } else {
                        tree = rightLeftRot(tree);
                    }
                }
            } else if (node.key < tree.key) {
                tree.left = add(tree.left, node);
                if (height(tree.left) - height(tree.right) == 2) {
                    if (node.key > tree.left.key) {
                        tree = leftRightRot(tree);
                    } else {
                        tree = leftLeftRot(tree);
                    }
                }
            }
        }
        tree.height = max(height(tree.left), height(tree.right)) + 1;
        return tree;
    }


    /**
     * 根据key值删除节点
     *
     * @param key
     */
    public void remove(int key) {
        remove(mRoot, key);
    }

    /**
     * 删除某个树下的key节点
     *
     * @param tree
     * @param key
     */
    private void remove(MyTreeNode tree, int key) {
        // TODO: 2022/2/15
    }

    /**
     * 平衡二叉树的旋转
     * 具体见：https://www.cnblogs.com/skywang12345/p/3577479.html
     * <p>
     * 平衡二叉树失去平衡的四种姿态
     * <p>
     * LL:LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，
     * 导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
     * <p>
     * LR:LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，
     * 导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
     * <p>
     * RR:RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，
     * 导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
     * <p>
     * RL:RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，
     * 导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
     * <p>
     * 以下是各种失去平衡状态下的旋转
     */

    /**
     * LL情况下的旋转
     *
     * @param tree
     * @return
     */
    private MyTreeNode leftLeftRot(MyTreeNode tree) {

        MyTreeNode node = tree.left;
        //首先将node.right赋值给tree.left,顺序不能乱，后面会改变node.right的值；
        tree.left = node.right;
        node.right = tree;

        //首先初始化tree的高度，应为旋转过后tree为node的右子树
        tree.height = max(height(tree.left), height(tree.right)) + 1;

        node.height = max(height(node.right), height(node.left)) + 1;

        return node;
    }

    /**
     * RR情况下的旋转
     *
     * @param tree
     * @return
     */
    private MyTreeNode rightRightRot(MyTreeNode tree) {
        MyTreeNode node = tree.right;
        //首先将node.left赋值给tree.right,顺序不能乱，因为后面node.left会重新进行赋值
        tree.right = node.left;
        node.left = tree;
        //首先初始化tree的高度，应为旋转过后tree为node的右子树
        tree.height = max(height(tree.left), height(tree.right)) + 1;

        node.height = max(height(node.right), height(node.left)) + 1;

        return node;
    }


    /**
     * LR情况下的旋转
     *
     * @param tree
     * @return
     */
    private MyTreeNode leftRightRot(MyTreeNode tree) {
        //首先使用RR
        MyTreeNode node = rightRightRot(tree.left);
        //再使用LL
        return leftLeftRot(node);
    }


    /**
     * RL情况下的旋转
     *
     * @param tree
     * @return
     */
    private MyTreeNode rightLeftRot(MyTreeNode tree) {
        //首先使用LL
        MyTreeNode node = leftLeftRot(tree.right);
        //再使用RR
        return rightRightRot(node);
    }

    private int max(int h1, int h2) {
        return h1 > h2 ? h1 : h2;
    }

    public class MyTreeNode {


        //树的高度
        private int height;

        //关键字
        private int key;

        //左子树
        private MyTreeNode left;

        //右子树
        private MyTreeNode right;

        public MyTreeNode(int key, MyTreeNode left, MyTreeNode right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }


}
